package primary.primary0;

import offer.offer02.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class S0199二叉树的右视图 {
    class Solution {
        /**
         * 82
         * 层序遍历，取最右边的那个
         */
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> deque = new ArrayDeque<>();
            if(root != null){
                deque.addLast(root);
            }
            while(!deque.isEmpty()){
                int layerLen = deque.size();
                for(int i = 0; i < layerLen; i++){
                    TreeNode curNode = deque.pollFirst();
                    if(curNode.left != null){
                        deque.addLast(curNode.left);
                    }
                    if(curNode.right != null){
                        deque.addLast(curNode.right);
                    }
                    if(i == layerLen - 1){
                        res.add(curNode.val);
                    }
                }
            }
            return res;
        }
    }
}
